<?php

class Lulco {
	
	const FINISHING_PERCENTAGE = 0.1;
	const NON_CONFLICTED_MUTATION_PROBABILITY = 0.01;
	const CONFLICTED_MUTATION_PROBABILITY = 0.9;
	const CROSS_PROBABILITY = 0.5;
	const CROSS_PORTION = 0.05;
	const INDIVIDUALS_COUNT = 20;
	const GENERATIONS_COUNT = 100;
	
	public function coloring(Graph $graph) {
		$generation = new Generation();
		
		for ($i = 0; $i < self::INDIVIDUALS_COUNT; $i++) {
			echo 'individual' . $i . "\n";
			$cloneGraph = new DBGraph($graph->getDbId());
			$cloneGraph->randomColoring();
			$generation->addIndividual($cloneGraph);
		}
		
		for ($i = 0; $i < self::GENERATIONS_COUNT; $i++) {
			echo 'generation ' . $i . "\n";
			$bestindividual = $generation->getBestIndividual();
			echo "colors " . $bestindividual->getColorsCount() . "\nfitness " . $bestindividual->getFitness() . "\n";
			var_dump($bestindividual->check());
			
			$toCross = array();
			$individualsCount = $generation->getIndividualsCount();
			$j = 0;
			foreach ($generation->getIndividuals() as $individual) {
				$j++;
				$individual = $this->finishColoring($individual);
				if ($individual->check()) {
					if ($individual->getColorsCount() <= ceil(1.1 * $individual->getBrelazColours())) {
						return $individual;
					}
				} else {
					if (count($toCross) == 1 && $j == $individualsCount) {
						$this->cross($toCross[0], $individual);
						$toCross = array();
					} elseif (count($toCross) == 0 && $j == $individualsCount) {
						$this->mutation($individual);
					} else {
						$rand = rand(0, 1000) / 1000;
						if ($rand < self::CROSS_PROBABILITY) {
							if (count($toCross) == 0) {
								$toCross[] = $individual;
							} else {
								$this->cross($toCross[0], $individual);
								$toCross = array();
							}
						} else {
							$this->mutation($individual);
						}
					}
				}
			}
		}
		return $this->finishColoring($generation->getBestIndividual(), true);
	}
	
	protected function cross(Graph $graph1, Graph $graph2, $crossCount = null) {
		if ($crossCount === null) {
			$crossCount = floor($graph1->getVerticesCount() * self::CROSS_PORTION);
		}
		
		for ($i = 0; $i < $crossCount; $i++) {
			$rand = rand(1, $graph1->getVerticesCount());
			foreach ($graph1->getVertices() as $vertex1) {
				if ($vertex1->getId() == $rand) {
					$color1 = $vertex1->getColor();
					break;
				}
			}
			
			foreach ($graph2->getVertices() as $vertex2) {
				if ($vertex2->getId() == $rand) {
					$color2 = $vertex2->getColor();
					$graph2->setVertexColor($vertex2, $color1);
					break;
				}
			}
			
			if ($vertex1) {
				$graph1->setVertexColor($vertex1, $color2);
			}
		}
	}
	
	protected function mutation(Graph $graph) {
		$conflictedVertices = $graph->getConflictedVertices();
		$nonConflictedVertices = $graph->getNonConflictedVertices();
		foreach ($conflictedVertices as $vertex) {
			$rand = rand(0, 1000) / 1000;
			if ($rand <= self::CONFLICTED_MUTATION_PROBABILITY) {
				$possibleColours = $graph->getPossibleColors($vertex);
				$color = $possibleColours[rand(0, count($possibleColours) - 1)];
				$graph->setVertexColor($vertex, $color);
			}
		}
		
		foreach ($nonConflictedVertices as $vertex) {
			$rand = rand(0, 1000) / 1000;
			if ($rand <= self::NON_CONFLICTED_MUTATION_PROBABILITY) {
				$possibleColours = $graph->getPossibleColors($vertex);
				$color = $possibleColours[rand(0, count($possibleColours) - 1)];
				$graph->setVertexColor($vertex, $color);
			}
		}
	}
	
	protected function finishColoring(Graph $graph, $forcedFinish = false) {
		
		$conflictedVertices = $graph->getConflictedVertices();
		if ($forcedFinish || count($conflictedVertices) / $graph->getVerticesCount() <= self::FINISHING_PERCENTAGE) {
			
			foreach ($conflictedVertices as $vertex) {
				$graph->setVertexColor($vertex, 0);
			}
			
			$brelaz = new BrelazWithRandom();
			$graph = $brelaz->coloring($graph);
		}
		return $graph;
	}
}

?>